#include<iostream>
#include<vector>
using namespace std;

//LeetCode 78 Subsets
vector<vector<int>> result;
vector<int> temp;
vector<int> sum;
int toSum(vector<int>& nums)
{
    int res = 0;
    for(auto& i : nums)
        res += i;
    return res;
}
bool isInSum(int n)
{
    if(n==0)
        return false;
    int target = toSum(temp)+n;
    for(auto& i : sum)
    {
        if(i == target)
            return true;
    }
    return false;
}
bool isHaveSame(int n)
{
    for(auto& i : temp)
    {
        if(n == i)
            return true;
    }
    return false;
}
void backtrack(vector<int>& nums, vector<int>& used)
{
    result.push_back(temp);
    if(temp.size() == nums.size())
        return;
    for(int i = 0; i < nums.size(); ++i)
    {
        if(!used[i]&&!isInSum(nums[i])&&!isHaveSame(nums[i]))
        {
            temp.push_back(nums[i]);
            used[i] = 1;
            backtrack(nums, used);
            temp.pop_back();
            used[i] = 0;
        }
    }
}
vector<vector<int>> subsets(vector<int>& nums) {
    vector<int> used(nums.size(), 0);
    backtrack(nums, used);
    return result;
}
int main()
{
    vector<int> nums = {0,1,2,3};
    vector<vector<int>> res = subsets(nums);
    for(auto& v : res)
    {
        for(auto& i : v)
            cout << i << " ";
        cout << endl;
    }
    return 0;
}